package BinaryTree;//给定一个二叉树，检查它是否是镜像对称的。
//
// 
//
// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
//
//     1
//   / \
//  2   2
// / \ / \
//3  4 4  3
// 
//
// 
//
// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
//
//     1
//   / \
//  2   2
//   \   \
//   3    3
// 
//
// 
//
// 进阶： 
//
// 你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 1601 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class isSymmetric {
    public boolean isSymmetric1(TreeNode root) {
        /**
         * 迭代法
         * */
        if(root==null || (root.left==null && root.right==null)) {
            return true;
        }
        //用队列保存节点
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点的左右孩子放到队列中
        queue.add(root.left);
        queue.add(root.right);
        while(queue.size()>0) {
            //从队列中取出两个节点，再比较这两个节点
            TreeNode left = queue.removeFirst();
            TreeNode right = queue.removeFirst();
            //如果两个节点都为空就继续循环，两者有一个为空就返回false
            if(left==null && right==null) {
                continue;
            }
            if(left==null || right==null) {
                return false;
            }
            if(left.val!=right.val) {
                return false;
            }
            //将左节点的左孩子， 右节点的右孩子放入队列
            queue.add(left.left);
            queue.add(right.right);
            //将左节点的右孩子，右节点的左孩子放入队列
            queue.add(left.right);
            queue.add(right.left);
        }

        return true;
    }

    public boolean isSymmetric(TreeNode root) {

        /**
         * 递归
         * */
        if(root==null ||(root.left==null&&root.right==null)){
            return true;
        }
        return check(root.left, root.right);

    }
    boolean check(TreeNode left, TreeNode right){
        /**
         * 对于一对左右节点，比较其内侧和外侧是否相等
         * */

        //若比较的 其中一个为null时 不可能对称
        if((left==null&&right!=null) || (left!=null&&right==null)){
            return false;
        }
        //若都为null，对称
        if (left == null && right == null) {
            return true;
        }
        //都不为null，但值不同,不对称
        if (left.val != right.val) {
            return false;
        }

        //比较外侧
        boolean lb = check(left.left, right.right);
        //比较内测
        boolean rb = check(left.right, right.left);
        return lb && rb;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
